package com.排序算法;

class Solution1{
    public void quickSort(int[] A,int startIndex,int endIndex){
        if(startIndex>=endIndex) return;//递归终止条件
        int pivotIndex=partition(A,startIndex,endIndex);//递归处理
        //开始递归
        quickSort(A,startIndex,pivotIndex-1);
        quickSort(A,pivotIndex+1,endIndex);
    }

    public int partition(int[] A,int left,int right){
        int pivot=A[left];//初始基准元素为数组或者子数组第一个元素
        while(left<right){
            //移动右指针
            while(left<right && A[right]>=pivot) --right;
            A[left]=A[right];
            //移动左指针
            while(left<right && A[left]<=pivot) ++left;
            A[right]=A[left];
            //也可以先移动后交换
        }
        A[left]=pivot;//将基准元素放入左指针的位置
        return left;//返回基准元素最终的位置
    }
}

public class 快速排序 {

    public static void main(String[] args) {
        int[] nums = { 1, 1, 3, 2, 5,1 };
        Solution1 s=new Solution1();
        s.quickSort(nums,0,nums.length-1);
        for (int num : nums) {
            System.out.println(num);
        }
    }
}
